// 给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种，返回所有可能

// 示例:

// 输入: 3
// 输出: 5
// 解释:
// 给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

//    1         3     3      2      1
//     \       /     /      / \      \
//      3     2     1      1   3      2
//     /     /       \                 \
//    2     1         2                 3

// =============================递归96===============================
/**
 * @param {number} n
 * @return {number}
 */
var numTrees = function (n) {
  if (n === 0) return 1;
  let num = 0;
  for (let i = 0; i <= n - 1; i++) {
    num += numTrees(i) * numTrees(n - i - 1);
  }
  return num;
};

// =============================优化递归96：记忆化===============================
/**
 * @param {number} n
 * @return {number}
 */
var numTrees = function (n) {
  // 记忆化memo为全局变量，而非递归内变量
  let memo = new Array(n + 1);
  let dfs = (n) => {
    if (n === 0) return 1;
    if (memo[n]) return memo[n];
    let num = 0;
    for (let i = 0; i <= n - 1; i++) {
      num += dfs(i) * dfs(n - i - 1);
    }
    memo[n] = num;
    return num;
  }
  return dfs(n)
};


// =============================递归95===============================
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number} n
 * @return {TreeNode[]}
 */
var generateTrees = function (n) {
  if (n === 0) return [];
  let dfs = (start, end) => {
    if (start > end) return [null];
    if (start === end) return [new TreeNode(start)];
    let res = [];
    for (let i = start; i <= end; i++) {
      let leftRes = dfs(start, i - 1);
      let rightRes = dfs(i + 1, end);
      for (left of leftRes) {
        for (right of rightRes) {
          let root = new TreeNode(i);
          root.left = left;
          root.right = right;
          res.push(root);
        }
      }
    }
    return res;
  }
  return dfs(1, n);
};

// =============================递归95优化：记忆化===============================
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number} n
 * @return {TreeNode[]}
 */
var generateTrees = function (n) {
  if (n === 0) return [];
  // 二维数组形式的备忘录
  let memo = new Array(n + 1);
  for (let i = 0; i <= memo.length - 1; i++) {
    memo[i] = new Array(n + 1);
  }
  let dfs = (start, end) => {
    if (start > end) return [null];
    if (start === end) return [new TreeNode(start)];
    if (memo[start][end]) return memo[start][end];
    let res = [];
    for (let i = start; i <= end; i++) {
      let leftRes = dfs(start, i - 1);
      let rightRes = dfs(i + 1, end);
      for (left of leftRes) {
        for (right of rightRes) {
          let root = new TreeNode(i);
          root.left = left;
          root.right = right;
          res.push(root);
        }
      }
    }
    memo[start][end] = res;
    return res;
  }
  return dfs(1, n);
};